package LeetCode._06小算法;
/*
    diff差分数组,每一个元素存放原数组当前元素与上一个元素的差
    也就是diff[i] = nums[i] - nums[i-1]
    从diff反推原数组只需要 res[i] = res[i-1]+diff[i]

    回想 diff 数组反推 nums 数组的过程，diff[i] += 3 意味着给 nums[i..] 所有的元素都加了 3，
    然后 diff[j+1] -= 3 又意味着对于 nums[j+1..] 所有元素再减 3，那综合起来，是不是就是对 nums[i..j] 中的所有元素都加3了？

    差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
 */
public class _02差分数组 {
    private int[] diff; //差分数组

    //构造差分数组
    public _02差分数组(int[] nums){
        assert nums.length>0;
        diff = new int[nums.length];
        //第一个值就是nums[0]的值，用于构造每一个元素的差分
        diff[0] = nums[0];
        for(int i=1;i<diff.length;i++){
            //当前元素 - 上一个元素 构造差分
            diff[i] = nums[i] - nums[i-1];
        }
    }

    /*
        给闭区间[i,j]增加val,只需要在差分数组diff[i] += 3,
        这样构造差分数组相当于构造原数组给res[i,length-1]都加上3,从构造原始数组就可以看出
        所以我们需要在res[j+1] -= 3,将多加的减去
     */
    public void increment(int i,int j,int val){
        diff[i] += val; //res[i,res.length-1] + 3
        if(j+1<diff.length){ //只有小于数组最后才能证明不是给[i,res.length-1]整个都加上3
            diff[j+1] -= val;
        }
    }


    //根据差分数组构造原数组
    public int[] result(){
        int[] res = new int[diff.length];
        res[0] = diff[0];
        for(int i=1;i<diff.length;i++){
            //差分数组的diff[i] = res[i] - res[i-1]
            //构造相当于 res[i] = diff[i] + res[i-1]
            res[i] = res[i-1] + diff[i];
        }
        return res;
    }
}
